/*
 * @Author: 缄默
 * @Date: 2021-11-22 21:19:26
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-08 22:00:18
 */

//最长递增子序列

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;




class Arr {
private:
    vector<int> num;
public:
    Arr(vector<int>& array);
    void lis1();
    void lis2();
    void print();
private:
    vector<int> getdp1();
    vector<int> getdp2();
    void generateLIS(vector<int>& dp);
};


void Arr::print() {
    for (auto x : num) {
        cout << x << " ";
    }
    cout << endl;
}

//构造函数
Arr::Arr(vector<int>& array) {
    for (auto i : array) {
        num.push_back(i);
    }
}

void Arr::lis1() {
    if (num.size() == 0) cout << "arr is empty";
    vector<int> dp = getdp1();
    return generateLIS(dp);
}

void Arr::lis2() {
    if (num.size() == 0) cout << "arr is empty";
    vector<int> dp = getdp2();
    generateLIS(dp);
}

//计算dp数组的时间复杂度为O（n2)
vector<int> Arr::getdp1() {
    vector<int> dp(num.size());
    for (int i = 0; i < num.size(); i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (num[i] > num[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return dp;
}

//用二分法查找当前数字所对应的最长字串的长度 同时利用ends记录下来本次查询所得到的数据
vector<int> Arr::getdp2() {
    vector<int> dp(num.size());
    vector<int> ends(num.size());
    ends[0] = dp[0];
    int right = 0;
    for (int i = 0; i < num.size(); i++) {
        int l = 0;
        int r = right;
        //二分法找到本数据在ends中对应的位置 第一个大于等于该数字的位置
        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] < num[i]) l = m + 1;
            else r = m -1;

        }
        //得到所在位置后判断该位置是否在ends范围内
        //不在的话扩大范围 同时把num[i]加入
        if (l > right) {
            right++;
            ends[right] = num[i];
            dp[i] = right;
        }
        //在的话 将num[i]替换掉对应的数字
        else {
            ends[l] = num[i];
            dp[i] = l;
        }
    }
    return dp;
}

void Arr::generateLIS(vector<int>& dp) {

    //遍历dp数组找到最大值及其所在位置
    int len = 0;
    int index = 0;
    for (int i = 0; i < dp.size(); i++) {
        if (dp[i] > len) {
            len = dp[i];
            index = i;
        }
    }

    //定义一个数组用来存放返回的序列
    vector<int> res(len);
    //先放入最大值
    res[--len] = num[index];
    //开始遍历该数组并找到所有返回序列
    for (int i = index; i >= 0; i--) {
        //dp数组中最长长度小1的位置且该处元素小于上一个元素
        if (num[i] < num[index] && dp[i] == dp[index] - 1) {
            res[--len] = num[i];
            index = i;
        }
    }
    for (auto x : res) {
        cout << x << " ";
    }
    cout << endl;
}

int main() {

    vector<int> arrs({2, 1, 5, 3, 6, 4, 8, 9, 7});
    Arr a = Arr(arrs);
    a.lis1();
    a.lis2();
    return 0;
}

